package LC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/binary-tree-level-order-traversal/description/
 * Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
 * For example:
 * Given binary tree [3,9,20,null,null,15,7],
 */
public class LC_102_BinaryTreeLevelOrderTraversal_Recur_BinaryTree_LevelOrder {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);
        List<List<Integer>> lists = Solution.levelOrder(root);
        System.out.println(lists);
    }

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode [val=" + val + ", left=" + left + ", right=" + right + "]";
        }
    }

    static class Solution {
        static List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> resultList = new ArrayList<>();
            if (root == null)
                return resultList;
            List<Integer> levelStorage = new LinkedList<>();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            queue.offer(null);
            while (queue.size() > 1) {
                TreeNode top = queue.poll();
                if (top == null) {
                    resultList.add(levelStorage);
                    queue.offer(null);
                    levelStorage = new LinkedList<>();
                } else {
                    levelStorage.add(top.val);
                    if (top.left != null)
                        queue.offer(top.left);
                    if (top.right != null)
                        queue.offer(top.right);
                }
            }
            resultList.add(levelStorage);
            return resultList;
        }
    }

}
